1. Field of the Invention
The invention relates generally to system software of computer systems, and deals more particularly with a method and system for improving memory defragmentation, particularly enabling chipcards to be defragmented.
2. Description and Disadvantages of Prior Art
A new area of technology with increasing importance is represented by the increasing use and acceptance of chipcards, sometimes called SmartCards and their applications for many different purposes.
Memory is a limited resource on chipcards. Thus, an optimum efficient usage of memory has to be envisaged generally.
During the usage of a chipcard repeated memory allocation operations are required for storing fresh data and repeated memory deallocation operations are required after deleting data in the memory of the chipcard. After a certain amount of usage in most chipcards the memory is used ineffectively as it is ‘fragmented’, i.e., there are a number of ‘valid’ data blocks distributed over the entire memory having ‘holes’ between them which are only difficult to use for further storage of data. For a right understanding of the wording provided herein it should be noted that a valid data block is meant to be a conventional set of data standing generally in a semantic context. ‘Valid’ is used for indicating that the contents of said block needs to be used by a program accessing the memory. ‘Valid’ stands in contrast to ‘hole’, indicating that in hole positions are no valid data, i.e., the unused gaps between the valid data blocks the use of the total size of them is the aim of the defragmentation procedure. Depending on the size of the data set being represented by the valid data block and the size of the copy chunks a copy operation of an entire data block can comprise a plurality of copy chunks, e.g., when the chunks are relatively small compared to the data block. In reverse, a whole data block can be contained in a single copy chunk, too. In application to SmartCards the memory is often an EEPROM and is divided into EEPROM pages as sub-unit having a size of e.g., 64 byte.
Today's Chipcards-have different flavors of memory organization. The EEPROM memory is a non-volatile memory which keeps personalized data of the chipcard holder. The typical applications today store a file system into the card which is more or less described in the ISO 7816/4 standard.
Other implementations might involve any blocks of data to be stored in the EEPROM. A general problem exists as mentioned above, whenever such blocks are deleted. This problem. is called the fragmentation of memory. It appears on deletion of a block. When a memory block or a file is deleted a ‘hole’ of unused memory is generated. New blocks being created may be larger than this hole, then they have to be allocated to the remaining free memory. If the newly created block is smaller than the existing hole it might fit in this or another hole, there will, however, in most of cases be another smaller hole created which results from the difference of the block size of the new block and the deleted block.
If blocks are deleted throughout the card's memory and other blocks are created frequently, the chipcard might contain an essential amount of unused memory holes which cannot be allocated as each of them is smaller than a requested block size. In this situation the chipcard would have to be fragmented in order to allocate additional memory space thereafter.
There are different approaches to reduce the impact of fragmentation. The memory may be organized in segments and each requested block is split up in sub-blocks of one segments size. This however leaves a hole of up to one segments size-one hole on each allocated block. Therefore this method is less effective for using the memory exhaustively. In Germany, the chipcard manufacturer ODS uses this system.
Another approach to reduce the impact of fragmentation is, to seek for that hole existing in the chipcard whose size does have the least difference from the requested block size, assumed, that the block size is yet smaller than the selected hole. This method is called the ‘Best-Fit-Algorithm’ and is the best known method to keep the impact of fragmentation small.
one obvious idea to solve the fragmentation problem is the defragmentation of the memory. Defragmentation per se is well known for hard disk drives, but not for chipcards. Available programs for hard disk defragmentation have been sold by different manufactures. Generally, the process of defragmentation copies the used memory blocks such, that the holes between two adjacent blocks are filled. After defragmentation all blocks are in continuos order, and no holes exist anymore between the blocks.
Defragmentation in chipcards, however, has been considered as not feasible by the state of the art operating system technology. Not feasible means that until now no approach has been presented which could be realized with an appropriate effort and performance and which could thus be applied within the limits of the available ROM on chipcards.
This situation is relevant for all currently discussed world wide projects, as e.g. JAVA cards, too, where the subject of ‘garbage collection’ could not be solved due to the existence of the defragmentation problem.
The defragmentation problem in chipcards appears in two flavors. The first problem comes from the organization of memory. Typically, the memory is organized such, that the physical addresses of memory locations are stored within the memory itself. A so-called ‘descriptor’ is intended to be general expression to mean any means for describing the location of a particular location in memory, and in particular pointers are thus understood by that. The descriptors mentioned during the course of description and in the claims are to be understood in that sense. Thus, a pointer is such a location which stores an address of another memory location. As most memory architectures are designed as ‘linked lists’ which is one of the most effective memory architectures those addresses are distributed all over the memory.
Also the file access mechanisms use fixed physical addresses in order to use files or blocks allocated in memory. A defragmentation of the memory would move memory blocks within the whole EEPROM range. Consequently, all references to physical addresses would have to be updated in the chipcard. This requires a high programming effort and will decrease the performance significantly as in most of the cases it will be impossible to reach two addresses to be written within one EEPROM page.
The other and decisive flavor of the defragmentation problem represents a problem which is much more difficult to solve during defragmentation of clipcards. Independent of the organization of the memory the defragmentation will always have to copy large chunks of memory. However, chipcards must be 100% resistant against power failure, i.e., any kind of power break-those generated by accident or others generated by intention during an attack to the card, for example.
Consequently it must be possible on a power break, to reconstruct the memory layout of the chipcard as to the beginning or to the end of the defragmentation.
The well known way to do the restoring is realized by so-called Backtrace or Write Forward Buffers, a reserved memory location in EEPROM which allows to hold the data layout prior to any alteration of the EEPROM. Those-buffers, however, cannot work in chipcards as their size must be larger than the size of any copied EEPROM range
As during a complete defragmentation process up to the whole EEPROM range might have to be copied, e.g., If a hole is in the very beginning of the EEPROM, and the memory space is a very limited resource on chipcards it is impossible to provide an appropriate Backtrace or write forward buffer to restore the EEPROM information after a possible power break.
Thus, in the state-of-the-art technology it is not possible to perform a defragmentation of the EEPROM in chipcards by keeping the rules of 100% power failure resistance.